package com.algrithom.pointer;

import java.util.Objects;
import java.util.Stack;

import com.common.model.ListNode;

public class Solution9 {
    
    public static void main(String[] args){
        ListNode<Integer> root = new ListNode<>(1);
        root.setNext(new ListNode<>(2));
        //        root.getNext().setNext(new ListNode<>(3));
        //        root.getNext().getNext().setNext(new ListNode<>(4));
        //        root.getNext().getNext().getNext().setNext(new ListNode<>(5));
        //        root.getNext().getNext().getNext().getNext().setNext(new ListNode<>(6));
        Solution9 solution9 = new Solution9();
        //        ListNode<Integer> result = solution9.removeNthFromEnd(root,6);
        ListNode<Integer> result = solution9.removeNthFromEnd2(root,1);
        while (Objects.nonNull(result)) {
            System.out.println(result.getVal());
            result = result.getNext();
        }
    }
    
    public ListNode<Integer> removeNthFromEnd(ListNode<Integer> head,int n){
        Stack<ListNode<Integer>> stack = new Stack<>();
        while (Objects.nonNull(head)) {
            stack.push(head);
            head = head.getNext();
        }
        if (stack.size() > n) {
            ListNode<Integer> preNode = stack.get(stack.size() - n - 1);
            preNode.setNext(stack.get(stack.size() - n + 1));
        } else {
            stack.remove(0);
        }
        return stack.get(0);
    }
    
    public ListNode<Integer> removeNthFromEnd2(ListNode<Integer> head,int n){
        ListNode<Integer> first = head.getNext();
        ListNode<Integer> second = head;
        for (int i = 0; i < n; ++i) {
            if (Objects.nonNull(first)) {
                first = first.getNext();
            }
        }
        if (Objects.isNull(first)) {
            return head.getNext();
        }
        while (first != null) {
            first = first.getNext();
            second = second.getNext();
        }
        second.setNext(second.getNext().getNext());
        return head;
    }
}
